1. Field of the Invention
The invention relates to dam communications systems and, more particularly, to the secure processing of messages therein using public key cryptography. The invention finds particular, though not exclusive, application to the generation of digital signatures.
2. Description of the Related Art
Public key cryptographic algorithms are widely used to certify the origin of or ensure the security or integrity of messages .in data communications systems. Various types of such algorithms exist of which one well known variant is the RSA algorithm. A general introduction to public key cryptography and the RSA algorithm can be found in: Meyer and Matyas `Cryptography--A New Dimension in Computer Data Security`, pages 32-48, Wiley 1982. These algorithms have some distinct advantages over the more traditional symmetric key algorithms. In particular, they provide the ability for a key to be published or certified so that any independent third party can receive and verify a message without reference to a central authority.
One example of the use of public key cryptography in data communications is in the generation of digital signatures. The principle behind these techniques is the creation of a public digital value--the signature--which depends on a message to be transmitted and the signing user, so the receiving user can be sure that the sending user, and no other user, could create the signature value, and that the user created the signature value for this message and no other.
In such systems, the party signing a message has a private key for which there exists a corresponding public key. The public key is available so that anyone can use it to decrypt data which the signer encrypts using the private key, but no-one can create such encrypted data without access to the private key.
Typically, the signer produces a hash value from the message using a strong hash algorithm, such that the chance of another message resulting in the same value is extremely low. The means of calculating this value is public knowledge but there is no feasible way to determine a different message which results in the same value. The signer encrypts the value using the private key, and sends the message and the encrypted value to the recipient.
The recipient can use the public key to decrypt the value, and can test whether the calculation on the message produces the same value. If it does, this satisfies the recipient that the message was the one signed because there is no feasible way to calculate another message which produces the same value. The recipient can also be sure that the signer did indeed sign the message because no-one can create the encrypted value without access to the private key.
However, such public key encryption schemes are computationally intensive and demand substantially higher computing resources, such as processing power and memory requirements, for encryption and decryption than symmetric key schemes.
In many applications of public key cryptography to data communications, the message must be processed under the control of a portable security device, such as a smart card, PCMCIA card or laptop computer, carried and presented by a user. Whilst methods have been proposed to enable messages to be signed with much less computational effort than they can be verified, such as in the US Department of Commerce/National Institue of Standards and Technology (NIST) Digital Signature Standard published in Federal Information Processing Standard (FIPS) 186, May 19, 1994, the situation remains that, using current technology, in many cases it is not practical or cost-effective to provide such portable security devices with the necessary processing power or memory to perform sufficiently strong public key processing in an acceptable time.
Various methods have been proposed in the prior art to enable such a security device to perform the public key processing with the aid of a powerful server computer, without requiring the security device to reveal the secret key to the server. Examples of these techniques can be found, for example, in: Laih et al, `Two efficient server-aided secret computation protocols based on the addition sequence`, Advances in Cryptology--Asiacrypt 91 Proceedings 1993 pp 450-459.
Whilst these methods go some way to alleviating the problem, they suffer from several disadvantages inherent in storing the secret key on a portable and low cost device.
First, it is possible the device may be probed to obtain the secret key.
Secondly, if the signer's private key is compromised, a different user might use it to process messages. In this circumstance, a means is required to revoke the secret key so the unauthorised user can no longer use it. Since the security devices are not connected to the system at all times and could be reconnected to the system at any point, withdrawing or preventing use of the secret keys is, in practice, very difficult. Typically this has been achieved using various types of user blacklists. However, there are many practical difficulties associated with controlling, updating and verifying the authenticity of such lists, particularly over widespread networks.
Furthermore, since some smart card implementations which make use of public key algorithms for signing purposes cannot generate the user's public and private key pair within the smart card, there are potential security exposures when the key is initially loaded into the security device. This is because the key generation algorithm is quite complex, more so than the encryption and decryption functions. Therefore if it is required to store the secret key on the card then it may also be required to generate the secret key off the card and to enter it onto the card during an initialisation process. This initialisation process inevitably exposes the key to some degree.